/*
* 优先级队列，队列最前是最小的值
* 利用最小堆的性质实现
*/
#ifndef PRIQUEUE_H
#define PRIQUEUE_H
const int MAXSIZE = 100;
const int INCSIZE = 2;//增大倍数

template<typename T>
class PriQueue
{
public:
	PriQueue()
		:maxsize(MAXSIZE), cursize(0)
	{
		data = new T[maxsize];
	}
	PriQueue(T* arr, int len);
	~PriQueue()
	{
		delete[]data;
		data = nullptr;
		cursize = 0;
		maxsize = 0;
	}

	int GetSize() const { return cursize; }
	bool IsEmpty() const { return cursize == 0; }
	T& GetFront() { if (!IsEmpty()) return data[0]; }
	const T& GetFront() const { if (!IsEmpty()) return data[0]; }
	void Pop();
	void Push(const T& x);

private:
	void FilterDown(int begin, int end);
	void FilterUp(int index);
	void MakeHeap();

private:
	T* data;
	int maxsize;
	int cursize;
};
#endif